package leetcode

import (
	"container/heap"
)

// findMaximizedCapital 根据给定的项目利润和资本，找到k个项目的最大利润。
// k: 可以完成的项目数量
// w: 初始资本
// profits: 每个项目的利润
// capital: 每个项目的启动资本
// 返回值: 最大化后的资本
func findMaximizedCapital(k int, w int, profits []int, capital []int) int {
	// n: 项目总数
	n := len(profits)
	// capitalUpHeap: 按资本升序排列的堆
	capitalUpHeap := &CapitalUpHeap{}
	// 将所有项目加入到capitalUpHeap中
	for i := 0; i < n; i++ {
		project := Project{profits[i], capital[i]}
		heap.Push(capitalUpHeap, project)
	}

	// profitDownHeap: 按利润降序排列的堆
	profitDownHeap := &ProfitDownHeap{}
	// 尝试执行k个项目，以最大化利润
	for k > 0 {
		k--
		// 将所有当前资本能够启动的项目从capitalUpHeap转移到profitDownHeap
		for capitalUpHeap.Len() > 0 && capitalUpHeap.Peek().startUpCapital <= w {
			heap.Push(profitDownHeap, heap.Pop(capitalUpHeap))
		}

		// 如果没有可以执行的项目，则提前退出循环
		if profitDownHeap.Len() == 0 {
			break
		}

		// 执行利润最大的项目，增加资本
		completeProject := heap.Pop(profitDownHeap).(Project)
		w += completeProject.profit
	}
	// 返回最大化后的资本
	return w
}

// Project 表示一个项目的利润和启动资本
type Project struct {
	profit         int
	startUpCapital int
}

// CapitalUpHeap 定义了按启动资本升序排列的项目堆
type CapitalUpHeap []Project

// Len 返回堆中元素的数量
func (h CapitalUpHeap) Len() int {
	return len(h)
}

// Less 比较两个项目的启动资本，用于维护堆的顺序
func (h CapitalUpHeap) Less(i, j int) bool {
	return h[i].startUpCapital < h[j].startUpCapital
}

// Swap 交换堆中两个项目的位置
func (h CapitalUpHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

// Peek 查看堆顶元素，即启动资本最小的项目
func (h CapitalUpHeap) Peek() Project {
	return h[0]
}

// Pop 从堆中移除并返回启动资本最小的项目
func (h *CapitalUpHeap) Pop() any {
	old := *h
	n := len(old)
	minCapitalProject := old[n-1]
	*h = old[0 : n-1]
	return minCapitalProject
}

// Push 向堆中添加一个项目
func (h *CapitalUpHeap) Push(x any) {
	*h = append(*h, x.(Project))
}

// ProfitDownHeap 定义了按利润降序排列的项目堆
type ProfitDownHeap []Project

// Len 返回堆中元素的数量
func (h ProfitDownHeap) Len() int {
	return len(h)
}

// Less 比较两个项目的利润，用于维护堆的顺序
func (h ProfitDownHeap) Less(i, j int) bool {
	return h[i].profit > h[j].profit
}

// Swap 交换堆中两个项目的位置
func (h ProfitDownHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

// Pop 从堆中移除并返回利润最大的项目
func (h *ProfitDownHeap) Pop() any {
	old := *h
	n := len(old)
	maxProfitProject := old[n-1]
	*h = old[0 : n-1]
	return maxProfitProject
}

// Push 向堆中添加一个项目
func (h *ProfitDownHeap) Push(x any) {
	*h = append(*h, x.(Project))
}
